The present invention relates to packet processing and, more particularly, to tuple-based packet lookup schemes.
Many packet switching nodes classify packets into flows in order to facilitate packet processing. Flows are often represented by tuples consisting of fields from the packet (source address, destination address, etc.) and properties associated with the packet (ingress port, quality of service, etc.). These tuples typically include an ordered string of bits representing the various flow properties forming the tuple.
In a conventional tuple-based packet processing operation, the tuple is applied to locate an entry within a flow information database having two halves—a key half, which matches the tuple, and a result half, which contains a payload used for processing packets within a flow defined by the tuple. Particularly, when the node receives a packet, it searches the database to find an entry with a key half that matches the tuple from the packet. When such an entry is found, the corresponding result half is retrieved and used to modify the packet, enqueue the packet for quality of service, and/or forward the packet out on one of the node's ports. This search-and-retrieve operation is commonly referred to as a lookup scheme.
One problem commonly encountered in configuring tuple-based lookup schemes is key size limitations. For example, a node's flow information database may only be able to accommodate keys containing 80 bits or fewer. Unfortunately, this maximum key size may be insufficient for a multi-property classification scheme that requires tuples having a larger number of bits. Another problem encountered in tuple-based lookup schemes is how to accomplish efficient “subnetting”, i.e. how to effectuate a lookup scheme that provides common processing to a group of distinct flows having some common flow properties in an efficient manner.